Content delivery networks (CDNs) or content distribution networks provide a caching infrastructure in IP networks to support multimedia services. A CDN performs a set of functions that handles things like placement of content into cache nodes, i.e. nodes that cache content, in the CDN, redirecting client requests to the most optimal cache node, keeping track of usage statistics and also replicating or moving content based on popularity in certain regions of the network. The mechanism to redirect clients to a cache node differs between different CDN implementations. Some use specially crafted DNS servers to direct users to the node caching the requested content and others use Hypertext Transfer Protocol (HTTP) or Real Time Streaming Protocol (RTSP) redirection to direct client requests to the node caching the requested content.
FIG. 1 schematically illustrates an example of a CDN 100. The network comprises a number of cache nodes, also called edge nodes 101-106 represented by filled circles wherein content, e.g. data files are cached only on edge nodes. In this example an end user computer 107, also called client, is connected to only one edge node 104. In this example one specific data file 108 is stored in two edge nodes 102, 103. The non-filled circles represent intermediate nodes 109 in the network that connects the edge nodes to each other. The lines between the circles represent links 110 between the nodes. The intermediate nodes 109 are e.g. routers and switches. Each link represents a communication cost, indicated by the letter “c”. The cost for different links can vary significantly depending on e.g. the connection and the distance between the nodes. For the sake of clarity the reference numerals c, 109 and 110 are only shown once in the figure.
A problem with a network as described above is to localize the “closest” cache node on which a copy of a requested data file is stored. In this case, “closest” means the cache node with the lowest path cost from the cache node to which the client is connected. The cost is a measure of the communication cost, and may include e.g. capacity, bandwidth constrains, jitter, delay, and average packet loss rate.
The problem of finding the closest cache node comprising a requested content can be solved for the real network model shown above. However, the algorithms are complex due to the multiple paths between cache nodes. Usually methods for finding a closest cache node is performed by a location server 120 (FIG. 1), also called locator node, upon receipt of a request from a cache node. Some examples of such methods are described below:
i) Each locator node serves requests from any cache node for any content. The locator node has information including: a distance table, which is a table comprising a matrix of entries each holding the distance between all pairs of cache nodes; and a content table, which is table of entries each holding the list of cache nodes caching the content. The distance is equivalent to the communication cost and the distance table can thus also be called cost table table. When receiving a request, the locator looks up the list of cache nodes caching the content in the content table. For each entry in the list, the distance between the requesting site and the hosting site is looked up in the distance table and the least distance site so far is remembered. Finally, the cache node having the shortest distance is determined and returned.
ii) Each locator node serves requests from any cache node for a subset of content. The distance table and content table are as in method i) above, but the content table only holds entries for the content served by the specific locator node. A request must first be redirected to the locator node serving the requested content. Once received, the appropriate locator node determines the best cache node as in the previous method i).
iii) A set of locator nodes serve requests from a specific cache node for any content. The locator node includes a content table as in method i) above, but the entries hold an ordered list of cache nodes. The ordering is obtained by pre-computing the distance from the served cache node to the different cache nodes caching a requested content and ordering the cache nodes accordingly. Non optimal cache nodes should be retained in the list in order to be able to update the list when a cache node caching the content is removed or added. A request is always served by a closest (local) locator node. Once a request is received, the locator node immediately looks up the first entry in the list of cache nodes hosting the content in the content table and returns it as the best cache node.
In the above described methods i) and ii) the needed storage capacity is proportional to the square number of cache nodes times the number of cached copies of content and in method iii) proportional to the number of cache nodes times the number of cached copies of content. In large networks this requires large memory capability in the locator node.
Further, the methods described above require significant processing capability.